package com.zhang.study.chapter05;

import java.util.Arrays;

import static com.zhang.util.RandomArrayUtil.generateRandomArray;

/**
 * 快速排序 荷兰国旗问题
 */
public class Code02_QuickSort01 {

    /**
     * 在数组 arr[left...right]中 以right为基准点，将数组分为两个部分，左边部分小于基准点，右边部分大于基准点
     *
     * @param arr   数组
     * @param left  左边界
     * @param right 右边界
     * @return 分割的下标
     */
    public static int partition(int[] arr, int left, int right) {
        if (left > right) {
            return -1;
        }
        if (left == right) {
            return left;
        }
        int less = left - 1;
        for (int i = left; i < right; i++) {
            if (arr[i] <= arr[right]) {
                swap(arr, ++less, i);
            }
        }
        swap(arr, ++less, right);
        return less;
    }

    private static void swap(int[] arr, int n1, int n2) {
        int temp = arr[n1];
        arr[n1] = arr[n2];
        arr[n2] = temp;
    }


    public static int[] partition2(int[] arr, int left, int right) {
        if (left > right) {
            return new int[]{-1, -1};
        }
        if (left == right) {
            return new int[]{left, right};
        }
        int less = left - 1;
        int more = right;
        int index = left;
        while (index < more) {
            if (arr[index] < arr[right]) {
                swap(arr, ++less, index++);
            } else if (arr[index] > arr[right]) {
                swap(arr, --more, index);
            } else {
                index++;
            }
        }
        swap(arr, more, right);
        return new int[]{less + 1, more};
    }


    public static void quickSort1(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process1(arr, 0, arr.length - 1);
    }

    public static void process1(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = partition(arr, left, right);
        process1(arr, left, mid);
        process1(arr, mid + 1, right);
    }


    public static void quickSort2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process2(arr, 0, arr.length - 1);
    }

    public static void process2(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int[] ints = partition2(arr, left, right);
        process1(arr, left, ints[0]);
        process1(arr, ints[1] + 1, right);
    }



    public static void quickSort3(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process3(arr, 0, arr.length - 1);
    }

    public static void process3(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        swap(arr, left + (int) (Math.random() * (right - left + 1)), right);
        int[] ints = partition2(arr, left, right);
        process3(arr, left, ints[0]);
        process3(arr, ints[1] + 1, right);
    }

    public static void main(String[] args) {
        int maxSize = 1000;
        int maxValue = 1000;
        int testTime = 50;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = arr1.clone();
            quickSort3(arr1);
            Arrays.sort(arr2);
            if (!Arrays.equals(arr1, arr2)) {
                System.out.println("Oops!");
                return;
            }
        }
        System.out.println("Nice!");

    }

}
